§ 1.1 Field of the Invention
The present invention concerns analyzing traffic (e.g., flow information) in a network, or inter-network. In particular, the present invention concerns generating traffic (e.g., flow) information for such analysis.
§ 1.2 Description of Related Art
The description of art in this section is not, and should not be interpreted to be, an admission that such art is prior art to the present invention.
Since the present invention may be used in the context of networks and inter-networks, both are introduced in § 1.2.1 below. Then, the need for network analysis is introduced in § 1.2.2 below. Finally, challenges to collecting information for network analysis are introduced in § 1.2.3 below.
§ 1.2.1 Networks and Inter-Networks
Many large networks are made up of interconnected nodes (referred to as “routers” in the specification below without loss of generality) for forwarding addressed data (referred to as “packets” in the specification below without loss of generality). The routers may be geographically distributed throughout a region and connected by links (e.g., optical fiber, copper cable, wireless transmission channels, etc.). In such a network, each router typically interfaces with (e.g., terminates) multiple input links and multiple output links. Packets traverse the network by being forwarded from router to router until they reach their destinations (as typically specified in by so-called layer-3 addresses in the packet headers). Unlike switches, which establish a connection for the duration of a “call” or “session” to send data received on a given input port out on a given output port, routers determine the destination addresses of received (ingress) packets and, based on these destination addresses, determine, in each case, the appropriate output link on which to send them. Since, unlike switches, routers are not connection-based—packets having the same destination address may actually traverse different paths through the network.
FIG. 1 illustrates an internet in which the present invention may be used. As illustrated in FIG. 1, an internet 100 may be viewed as a number of sub-networks or “autonomous systems” (also referred to as “AS”) 110, 150. Different entities (such as Internet service providers (“ISPs”)) may own and/or operate different autonomous systems. A routing algorithm for use within an autonomous system is called an “interior gateway protocol” (“IGP”), while a routing algorithm for use between autonomous systems is called an “exterior gateway protocol” (“EGP”). Known exterior gateway protocols include the “border gateway protocol” (“BGP”).
Some autonomous systems (ASes) may become quite large, and their management may become quite complex. In such instances, hierarchical routing techniques may be used to define the large autonomous system as a number of smaller regions. Typically, routers within a given region only know the detailed topology of the network within their region, know how to get to other regions, and know the addresses of nodes contained in the other regions (or just those nodes contained in a backbone area). Thus, hierarchical routing techniques serve to reduce the complexity of routers by shielding the complexity of the network beyond a router's region. The cost, however, of this reduced complexity is that globally shortest paths are not necessarily determined.
Referring to the autonomous system 150 of FIG. 1, the open shortest path first (“OSPF”) interior gateway protocol may divide the autonomous system 150 into a number of areas 154, each of which is connected with a backbone area 152. Routers can be classified as follows. “Internal routers” are wholly within one area (See, e.g., routers 153, 160.), “area border routers” connect two or more areas (See, e.g., router 158.), “backbone routers” are in the backbone (See, e.g., router 153.), and “AS boundary routers” neighbor routers in other autonomous systems (See, e.g., routers 112 and 156.). Notice that a given router may belong to more than one class.
§ 1.2.2 The Need for Network Analysis
Recall that different network service providers (e.g., ISPs) may own and/or manage various autonomous systems (ASs). Such providers want to analyze traffic within their network, traffic entering their network from another network (another AS), and traffic leaving their network to another network (another AS). Such traffic analysis may be used when planning capacity, when defining a hierarchical network within an autonomous system, for billing and accounting, and for developing or updating arrangements with the other network service providers (such as peering agreements for example).
For example, if much of a network service provider's traffic goes through another autonomous system, and it has to compensate the owner of that autonomous system (e.g., pursuant to a peering agreement), it may decide to extend its network to avoid that other autonomous system. Alternatively, it may decide that it needs to add more capacity at the gateway between its system and the other autonomous system, or it may decide that it needs to add additional peering points (e.g., AS boundary routers). As another example, if a network service provider services much more traffic from another network service provider than that other network service provider services for it, it may want to be compensated by the other network service provider.
§ 1.2.3 Challenges to Gathering Data for Network Analysis
Often, forwarding devices such as routers are equipped to sample packets, or at least header information in such packets, accepted and forwarded. Unfortunately, however, such samples often will not include information used by traffic analysis tools. For example, such traffic analysis tools will often want network and inter-network information (also referred to as “path-centric” information) not included in such samples. Accordingly, there is a need to associate such samples with information used by traffic analysis tools. Given the potentially large number of packets, such techniques for associating the samples with path-centric information should be efficient, both in terms of processing time and storage. Moreover, it may be desirable to provide various parameters to be analyzed by traffic analysis tools in a convenient form. The generation of such parameters in a convenient form should be efficient, both in terms of processing time and storage.